import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 滑动窗口+哈希表
// 先记录每个单词的出现次数
// 接着用固定的窗口长度来对字串进行匹配
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }

        int wordLen = words[0].length();
        int totalWords = words.length;
        int totalLen = wordLen * totalWords;
        int sLen = s.length();

        if (sLen < totalLen) {
            return result;
        }

        // 统计 words 中每个单词的出现次数
        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        // 滑动窗口遍历 s
        for (int i = 0; i <= sLen - totalLen; i++) {
            String currentSubstring = s.substring(i, i + totalLen);
            Map<String, Integer> tempCount = new HashMap<>();

            // 分割子串并统计单词频率
            for (int j = 0; j < totalLen; j += wordLen) {
                String currentWord = currentSubstring.substring(j, j + wordLen);
                tempCount.put(currentWord, tempCount.getOrDefault(currentWord, 0) + 1);
            }

            // 检查是否匹配
            if (tempCount.equals(wordCount)) {
                result.add(i);
            }
        }

        return result;
    }
}